Forms of communication and data transmission make use of low-density parity-check codes (LDPC). LDPC codes are a form of linear error correcting code, which are used to transmit messages over a noisy transmission channel. When a transmitter uses an LDPC code to encode data, it encodes it in a redundant form. This redundancy allows the receiver to detect a limited number of errors that may occur anywhere in the message, and also allows the receiver to correct these errors without retransmission of data. LDPC codes are powerful block codes whose performances get close to Shannon capacity as their block size increases. As a result, efficient and high performing LDPC codes have been standardized by several standardization bodies, the first being DVB-S2. In DVB-S2 two different coded block sizes have been used: 64800 and 16200 bits. LPDC codes are finding increasing use in applications where reliable and highly efficient information transfer over bandwidth in the presence of data-corrupting noise. LPDC codes are currently utilized in digital video broadcasting, microwave communications, cell phone communications, and Wi-Fi.
FIG. 1 illustrates an example system 100. As illustrated in the figure system 100 includes a gateway 102, a user terminal 104, a user terminal 106, a user terminal 108, a user terminal 110, a user terminal 112, and the internet 114. User terminal 104 is arranged to send code blocks, which are 120 bits in length, to gateway 102 along bi-directional transmission line 116. User terminal 106 is arranged to send code blocks, which are 240 bits in length, to gateway 102 along bi-directional transmission line 118. User terminal 108 is arranged to send code blocks, which are 360 bits in length, to gateway 102 along bi-directional transmission line 120. User terminal 110 is arranged to send code blocks, which are 480 bits in length, to gateway 102 along bi-directional transmission line 122. User terminal 112 is arranged to send code blocks, which are 600 bits in length, to gateway 102 along bi-directional transmission line 124. For purposes of discussion, in this example, each user terminal is transmitting discrete code blocks of a certain length. In practice, each user terminal is operable to transmit a plurality of code block lengths, which are dependent on the amount of information to be transmitted.
Gateway 102 is arranged to send and receive data from, bi-directional transmission line 116 from user terminal 104, bi-directional transmission line 118 from user terminal 106, bi-directional transmission line 120 from user terminal 108, bi-directional transmission line 122 from user terminal 110, and bi-directional transmission line 124 from user terminal 112. Gateway 102 is additionally arranged to send encoded data stream 126 to internet 114. Gateway 102 contains a LDPC code and architecture for each respective code block length that it supports. In this example, gateway 102 contains an LDPC code and architecture set for each of the code block it supports, the lengths of which are 120 bits, 240 bits, 360 bits, 480 bits, and 600 bits.
In operation, a user will send code blocks to gateway 102 from a user terminal. Each individual user terminal encodes the data with an LDPC encoder and then sends the encoded data blocks to gateway 102. When gateway 102 receives the encoded LDPC code blocks, it decodes them using an LDPC decoder to obtain the originally transmitted data. Note that when gateway 102 wants to send data to a user terminal the process is reversed. When gateway 102 wants to send data to a user terminal, it uses an LDPC encoder to encode the data. Once the data is encoded, the encoded code blocks are transmitted to a user terminal, which then decodes the code blocks to obtain the originally transmitted data. Once the data is encoded, it may be sent to internet 112 via internet connection 126.
Data being sent over a noisy channel needs to be sent in a secure form. When a transmission channel is noisy it is much easier to lose data during transmission. This can create difficulties because of transmission control protocol (TCP). Each data packet that is sent has a sequence number that is used to reconstruct the transmitted data in the correct order. For successful communication, the reliability of each packet (i.e. robustness against the channel noise) needs to be similar.
Another difficulty to consider during data transmission is that of power consumption. The larger a data packet is, the less energy per bit is consumed during transmission. This is due to the fact that the performance of modern error correcting codes, such as LDPC or turbo codes, improves with increasing block size. For very large data streams it becomes very important to try and minimize energy consumption. For example, if a user wants to send a data stream that is 120,000 bits long, it would be much more efficient to send 20 packets that are 6000 bits in length than it would be to send 3000 packets that are 40 bits in length.
Data streams that are being transmitted first need to be configured into a data stream length that is supported be the receiver it is being sent to. This will be further illustrated by FIGS. 2-4B.
FIG. 2 illustrates an example of various data stream lengths as well as supported data stream lengths of system 200. As illustrated in the figure system 200 includes data stream sizes that are integer multiples of 120 bits. Data stream 202, data stream 206, data stream 212, data stream 222, and data stream 230 represent the data stream lengths that are supported by the system hardware. Data stream 202 through data stream 230 represents all possible incoming data stream lengths. Note that it is possible of for an incoming data stream to exceed the possible supported data stream size but for the purposes of discussion there is a cut off at 1800 bits represented by data stream 230.
FIG. 3A and FIG. 3B illustrates the transmission of a data stream size that is not supported by the receiver hardware. As illustrated in FIGS. 3A-3B system 300 includes supported data stream 222, data stream length 224, a data packet 326 and a data packet 328. Supported data stream length 222 is the length of 11 data packets, each of which is 120 bits in length. Data stream 224 is comprised of 12 individual data packets, data packet 302 through data packet 324, each of which is 120 bits in length. Data packet 326 is a packet that can hold 11 data packets each of which are 120 bits in length. Data packet 328 is a packet that can hold 11 data packets each of which are 120 bits in length. In operation, data stream 224 needs to be converted into a data stream, of two or more pieces, with lengths that can be put into data packets that are supported by the receiver hardware. Since data stream 224 is too long to fit into data packet 322, it needs to be divided up into smaller lengths that will fit into a supported data packet size that will then be transmitted. The division of data stream 224 into smaller lengths to fit into supported data packet sizes will be further discussed in reference to FIG. 3B.
FIG. 3B illustrates an example data stream that has been divided into smaller stream lengths that can fit into data packets which are supported by the receiver hardware. In operation, data stream 224 has been divided into two lengths, which are small enough to fit into supported data packet 326 and data packet 328, both of which are the same length as supported data packet 222. Data packet 326 is filled with data packet 302 through data packet 322 from data stream 224 leaving data packet 324 left over. Data packet 328 contains data packet 324 from data stream 224 but is otherwise empty. Since a data packet can't be sent unless it is full, the open space is filled with dummy bits. Dummy bits do not affect the content of data packet 328; they are simply placed in data packet 328 to fill it so it may be transmitted. At this point, data stream 224 has been divided into two smaller lengths that have been put into data packet 326 and data packet 328, and they are ready to be transmitted to the receiver.
FIG. 4A and FIG. 4B illustrate the transmission of a data stream length that is not supported by receiver hardware. As illustrated in FIGS. 4A-4B system 400 includes supported data stream length 206, data stream 224, a data packet 402, a data packet 404, a data packet 406, and a data packet 408. Supported data stream length 206 is the length of 3 data packets, each of which is 120 bits in length. Data stream 224 is comprised of 12 individual data packets, data packet 302 through data packet 324, each of which is 120 bits in length. Data packet 402, data packet 404, data packet 406, and data packet 408 can each hold 3 packets of data, each of which are 120 bits in length. In operation, data stream 224 needs to be converted into a data stream lengths that can be put into packet sizes that are supported by the receiver hardware. Since data stream 224 is too long to fit into data packet 402, it needs to be divided up into smaller lengths that will fit into a supported data packet size that will then be transmitted. The division of data stream 224 into smaller lengths to fit into supported data packet sizes will further be discussed in reference to FIG. 4B.
FIG. 4B illustrates an example data stream that has been divided into smaller stream lengths which are able to fit into data packet which are supported by the receiver hardware. In operation, data stream 224 has been divided into 4 equal lengths, each of which are small enough to fit into data packet 402, data packet 404, data packet 406, or data packet 408. Each data packet is filled with information from data stream 224. Once data packet 402, data packet 404, data packet 406, and data packet 408 are filled with information from data stream 224, they are ready to be transmitted to the receiver.
There are several problems with the current methods when utilizing LDPC codes. The first problem is that of large block size support as shown in FIGS. 3A-4B.
A code block may sometimes need to be very small and sometimes very large. If only a large block size was implemented, a lot of transmission capacity would be wasted when the user had only a small amount of data to send. Conversely, if only a small block size was implemented, more power would be used than necessary when the user had a large amount of data to send since the performance of iterative decoding systems improve as the block size increases. Even though a user may have an arbitrarily large amount of data to send occasionally, it would not be practically feasible to implement arbitrarily large block sizes. That's because the complexity of iterative receivers increases almost linearly with increasing block sizes. Another problem with the current methods of utilizing LDPC codes, is the lack of intermediate block size support as shown in FIG. 1. If one wants to support many different code block lengths that it may be undesirable to design a separate LDPC code for each block length. The final problem with the current methods for utilizing LDPC codes as shown in FIG. 1 is the space that is taken up by the architecture used for each LDPC code. If one wants to support many different code block lengths, an LDPC code and its respective architecture needs to be implemented in the hardware design for each individual code block length.
To support many different code block lengths, the architecture needed to support each individual code block length begins to be problematic. As the number of architectures being implemented for each code block length increases, the complexity of the hardware design increases as well. The increase in complexity, for each supported code block length, is too high when attempting to design hardware that is capable of supporting many code block lengths.
What is needed is a system and method to address the problem of large block size support. The transmitted block sizes need to be chosen so that the minimum transmitted size is maximized. This means that when a user wants to transmit more data than the maximum supported block size, the transmitted block sizes should be as large as possible without having empty space in the transmitted block.
What is needed is a system and method to address the problem of intermediate block size support. To address intermediate block size support, bits in the code should be shortened, punctured, and repeated to derive intermediate code block lengths. On the other hand, the location of punctured bits should be carefully chosen in order not to cause substantial performance loss. What is needed is a system and method for using common decoder architecture for different code rates and block sizes. It may also be desirable to use the same piece of hardware to decode all block sizes and all code rates with the help of a code-specific set of parameters. This will reduce the complexity of the receiver where a different decoder is used for different codes.